package day_2022_9_to_12.Day;

import java.util.*;

/**
 * @author haomin
 * @date 2022/09/12 22:09
 **/
public class Day10_3_Num301_RemoveInvalidParentheses {
    class Solution {
        public List<String> removeInvalidParentheses(String s) {
            List<String> res = new ArrayList<>();
            if(s.equals("()") || s.equals("")){
                res.add(s); return res;
            }
            Deque<String> q = new LinkedList<>();
            HashSet<String> set = new HashSet<>();
            q.offer(s);
            boolean flag = false;
            while(!q.isEmpty()) {
                String cur = q.poll();
                if(isValid(cur.toCharArray())){
                    res.add(cur);
                    flag = true;
                }
                if(flag) continue;
                flag = false;

                for(int i = 0; i < cur.length(); ++i){
                    if(cur.charAt(i) == '(' || cur.charAt(i) == ')'){
                        String ret = "";
                        if(i == cur.length()-1){
                            ret = cur.substring(0, cur.length()-1);
                        }else {
                            ret = cur.substring(0,i)+cur.substring(i+1);
                        }
                        if(set.add(ret)) q.offer(ret);
                    }
                }
            }
            if(res.size() == 0) res.add("");
            return res;
        }
        private boolean isValid (char[] ch){
            int count = 0;
            for(char c : ch){
                if(c == '(') count++;
                if(c == ')'){
                    if(count > 0) count--;
                    else return false;
                }
            }
            return count == 0;
        }
    }
}